import Glibc
class Timer {
    private let CLOCK_REALTIME = 0
    private var start_timespec = timespec()
    private var end_timespec = timespec()
    private var time_spec = timespec()
    func start() {
        clock_gettime(Int32(CLOCK_REALTIME),&start_timespec)
    }
    
    func stop() -> Double {
        clock_gettime(Int32(CLOCK_REALTIME),&end_timespec)
        let start_time = Double(start_timespec.tv_sec * 1_000_000 + start_timespec.tv_nsec / 1_000)
        let end_time = Double(end_timespec.tv_sec * 1_000_000 + end_timespec.tv_nsec / 1_000)
        let time = end_time - start_time
        return time / 1_000
    }
    func getTime() -> Double {
        clock_gettime(Int32(CLOCK_REALTIME),&time_spec)
        return Double(time_spec.tv_sec * 1_000_000 + time_spec.tv_nsec / 1_000)
    }
}
var suites: Array<BenchmarkSplay> = [];
var scores: Array<String> = []


// Configuration.
var splayTreeSize: Int = 8000;
var splayTreeModifications: Int = 80;
var splayTreePayloadDepth: Int = 5;
// todo
var splayTree: SplayTree!;
var splaySampleTimeStart: Double = 0.0;
var splaySamples: Int = 0;
var splaySumOfSquaredPauses: Double = 0;
//reference in set for calculate Splay score
var reference: Array<Int> = [81491, 273];

class BenchmarkSplay {
    var name: String
    var run: () -> String

    init(name: String, run: @escaping () -> String) {
        self.name = name
        self.run = run
        suites.append(self)
    }
static func sumScores() -> String {
    var num = 0
    let len = scores.count
    
    for j in 0..<len {
        num += Int(scores[j]) ?? 0
    }
    
    return String(num)
}

func RunSuites(singleItem: String?)->Int {
    var scores = [String]()
    let length = suites.count
    for i in 0..<length {
        self.runSingleBenchmark(index: i, name: suites[i].name)
    }

    let scoreTotal = BenchmarkSplay.sumScores()
    // notifyScore(scores: scoreTotal)
    return Int(scoreTotal)!
}
  
func runSingleBenchmark(index: Int, name: String) {
    do {
        let result = try suites[index].run()
        notifyResult(name: name, result: result)
        scores.append(result)
    } catch {
        notifyError(name: name)
    }
}

func  notifyResult(name: String, result: String)
{
    print(name + ":\t " + result + "\tms");
} 

func  notifyError(name: String)
{
    print(name + "error");
} 
func  notifyScore(scores: String)
{
    print("scores:" + scores);
} 

static func countBenchmarks() -> Int {
    let count = suites.count
    return count
}

 static func ResetRNG() {
    /*
	Double.random = {
        var seed = 49734321
        return {
            // Robert Jenkins' 32 bit integer hash function.
            seed = ((seed + 0x7ed55d16) + (seed << 12)) & 0xffffffff
            seed = ((seed ^ 0xc761c23c) ^ (seed >> 19)) & 0xffffffff
            seed = ((seed + 0x165667b1) + (seed << 5)) & 0xffffffff
            seed = ((seed + 0xd3a2646c) ^ (seed << 9)) & 0xffffffff
            seed = ((seed + 0xfd7046c5) + (seed << 3)) & 0xffffffff
            seed = ((seed ^ 0xb55a4f09) ^ (seed >> 16)) & 0xffffffff
            return Double(seed & 0xfffffff) / 0x10000000
        }
    }()
	*/
}

static func FormatScore(value: Double) -> String {
    return String(Int(round(value)))
	}
}

class Benchmark {
  var name: String
  var doWarmup: Bool
  var doDeterministic: Bool
  var run: () -> ()
  var setup: () -> ()
  var tearDown: () -> ()
  var rmsResult: () -> Double
  var minIterations: Int
  var data: (runs: Int, elapsed: Double)?

  init(name: String, doWarmup: Bool, doDeterministic: Bool, run: @escaping () -> (),
       setup: (() -> ())? = nil, tearDown: (() -> ())? = nil, rmsResult: (() -> Double)? = nil, minIterations: Int = 32) {
    self.name = name
    self.doWarmup = doWarmup
    self.doDeterministic = doDeterministic
    self.run = run
    self.setup = setup!
    self.tearDown = tearDown!
    self.rmsResult = rmsResult!
    self.minIterations = minIterations
    self.data = nil
  }

func RunNextSetup(_ benchmarkResult: BenchmarkResult) {
    do {
        self.setup()
    } catch let error {
        print("\(self.name)setup: \(error)")
    }
    self.runNextBenchmark(benchmarkResult: benchmarkResult)
}

func runNextBenchmark(benchmarkResult: BenchmarkResult) {
    do {
        self.runSingle(benchmarkResult: benchmarkResult)
    } catch let error {
        print("\(self.name)RunNextBenchmark: \(error)")
    }
    self.data == nil ? self.runNextTearDown() : self.runNextBenchmark(benchmarkResult: benchmarkResult)
}

func runNextTearDown() {
    do {
        self.tearDown()
    } catch let e {
        print("\(name)RunNextTearDown: \(e)")
    }
}


func runSingle(benchmarkResult: BenchmarkResult) {
    // Sets up data in order to skip or not the warmup phase.
    if !doWarmup && data == nil {
        data = (runs: 0, elapsed: 0)
    }
     
    if data == nil {
        measure()
        data = (runs: 0, elapsed: 0)
        print("rms data nil")
    } else {
        measure()
        // If we've run too few iterations, we continue for another second.
        if data!.runs < minIterations { return }
        let usec = (Double(data!.elapsed) * 1000) / Double(data!.runs)
        let rms = (rmsResult != nil) ? rmsResult() : 0
        benchmarkResult.time = usec
        benchmarkResult.latency = rms
	    print("rms: " + String(rms))
        data = nil
    }
}

func measure() {
    var elapsed: Double = 0
    var start:Double = 0
    let timer = Timer()
    timer.start()
    // Run either for 1 second or for the number of iterations specified
    // by minIterations, depending on the config flag doDeterministic.
    var i = 0
	if (doDeterministic) {
		while i < minIterations {
	    	run()
            elapsed = timer.stop()
			i += 1
        }
	} else {
		while Int(elapsed) < 1000 {
			run()
            elapsed = timer.stop()
			i += 1
        }
	}
	

    if var data = data {
	        self.data!.runs += doDeterministic ? minIterations : i
        self.data!.elapsed += elapsed
    }
}
}

class BenchmarkResult {
    var benchmark: String
    var time: Double
    var latency: Double

    init(benchmark: String, time: Double, latency: Double) {
        self.benchmark = benchmark
        self.time = time
        self.latency = latency
    }
}


func runSplay() -> String {

    let benchmark = Benchmark(name: "Splay", doWarmup: true, doDeterministic: false, run: SplayRun, setup: SplaySetup, tearDown: SplayTearDown, rmsResult: SplayRMS)
    var benchmarkResult = BenchmarkResult(benchmark: "Splay", time: 0, latency: 0)
    BenchmarkSplay.ResetRNG()
    benchmark.RunNextSetup(benchmarkResult)
    let score = benchmarkResult.time
    let formatted = BenchmarkSplay.FormatScore(value: score)
    if reference.count == 2 && benchmarkResult.latency != 0 {
        let scoreLatency = benchmarkResult.latency / Double(reference[1])
        let formattedLatency = BenchmarkSplay.FormatScore(value: 100 * scoreLatency)
        print(benchmark.name + "Latency: " + formattedLatency)
    }
    return formatted
}


func GeneratePayloadTree(_ depth: Int,_ tag: String) -> NodeValue {
    if (depth == 0) {
	    let resultArray: Array<Int> = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
        let resultString = "String for key " + tag + " in leaf node";
		return NodeValue((resultArray, resultString), nil, nil);
    } else {
        return NodeValue(nil, GeneratePayloadTree(depth - 1, tag), GeneratePayloadTree(depth - 1, tag));
    }

    var curDep = depth

    let left: NodeValue? = NodeValue(nil, nil, nil)
    let right: NodeValue? = NodeValue(nil, nil, nil)
    let top: NodeValue! = NodeValue(nil, left, right)

    var inArray: Array<NodeValue> = Array(repeating: NodeValue(nil, nil, nil), count: 2 << (depth - 1))
    var outArray: Array<NodeValue> = Array(repeating: NodeValue(nil, nil, nil), count: 2 << (depth - 1))
    inArray[0] = top

    while (curDep != 0) {
        curDep -= 1
        var nodeNum: Int = 1
        if (depth - curDep - 1 > 0) {
            nodeNum = 2 << (depth - curDep - 2)
        }

        for i in 0..<nodeNum {
            let node = inArray[i]
            if (curDep > 0) {
                let left1: NodeValue? = NodeValue(nil, nil, nil)
                let right1: NodeValue? = NodeValue(nil, nil, nil)
                let left2: NodeValue? = NodeValue(nil, nil, nil)
                let right2: NodeValue? = NodeValue(nil, nil, nil)

                node.left! = NodeValue(nil, left1, right1)
                node.right! = NodeValue(nil, left2, right2)
                outArray[2 * i] = node.left!
                outArray[2 * i + 1] = node.right!
            } else {
                let resultArray: Array<Int> = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
                let resultString = "String for key " + tag + " in leaf node";
                node.left! = NodeValue((resultArray, resultString), nil, nil)
                node.right! = NodeValue((resultArray, resultString), nil, nil)
            }
        }

        let tmpArray = inArray
        inArray = outArray
        outArray = tmpArray
    }
    return top
}

func GenerateKey() -> Double {
    // The benchmark framework guarantees that Math.random is deterministic
    return Double.random(in: 0...1);
}

func SplayRMS() -> Double {
    print(" splaySumOfSquaredPauses" + String(splaySumOfSquaredPauses) + " splaySamples" + String(splaySamples))
    return round(Double((splaySumOfSquaredPauses / Double(splaySamples)).squareRoot() * 10000));
}

func SplayUpdateStats(_ time: Double) {
    let pause: Double  = time - splaySampleTimeStart;
    splaySampleTimeStart = time;
    splaySamples += 1;
    splaySumOfSquaredPauses += pause * pause;
}

func InsertNewNode() -> Double {
    // Insert new node with a unique key.
    var key: Double;
    repeat {
        key = GenerateKey();
    } while (splayTree.find(key) != nil);
    let payload = GeneratePayloadTree(splayTreePayloadDepth, String(key));
	splayTree.insert(key, payload);
    return key;
}

func SplaySetup() {
    splayTree = SplayTree();
    splaySampleTimeStart = Timer().getTime() / 1000;
	var i: Int = 0;
    while i < splayTreeSize
		{
        InsertNewNode();
        if ((i + 1) % 20 == 19) {
		    // timeInterval = Date().timeIntervalSince1970;
            SplayUpdateStats(Timer().getTime()/1000);
        }
		i += 1;
    }
}


func SplayTearDown() {
    let keys: Array<Double> = splayTree.exportKeys();
    splayTree = nil;

    splaySamples = 0;
    splaySumOfSquaredPauses = 0;

    // Verify that the splay tree has the right size.
    let length: Int = keys.count;
    if (length != splayTreeSize) {
        print("Splay tree has wrong size" + String(length));
		// throws Error;
    }

    // Verify that the splay tree has sorted, unique keys.
    var i: Int = 0;
	while i < length - 1
	{
        if (keys[i] >= keys[i + 1]) {
            print("Splay tree not sorted");
			// throws Error;
        }
		i += 1;
    }
}

func SplayRun() {
    // Replace a few nodes in the splay tree.
	var i: Int = 0;
    while i < splayTreeModifications
	{
        let key: Double = InsertNewNode();
        let greatest: Node? = splayTree.findGreatestLessThan(key);
        if (greatest == nil) {
		    splayTree.remove(key);
		} else {
		    splayTree.remove((greatest!.key!));
		}
		i += 1;
    }

    SplayUpdateStats(Timer().getTime() / 1000);
}

class NodeValue {
    var value: ([Int], String)?;
    var left: NodeValue?;
    var right: NodeValue?;

    init(_ value: ([Int],String)?,_ left: NodeValue?,_ right: NodeValue?)
    {
        self.value = value;
        self.left = left;
        self.right = right;
    }
}

class Node {
    var key: Double?;
    var value: NodeValue?;  // Todo TS value | two types
    var left: Node?;
    var right: Node?;

    init(_ key: Double?,_ value: NodeValue?)
    {
        self.key = key;
        if (value != nil) {
            self.value = value;
        } else {
		    self.value = nil;
		}
    }

    func traverse_(_ f: ((Node)->())) {
        var current: Node? = self;
        while current != nil
		{
            let left: Node? = current!.left;
            if (left != nil) {
			    left!.traverse_(f);
			}
            f(current!);
            current = current!.right;
        }
    }
}

class SplayTree {
    var root_: Node?;

    init() {
        self.root_ = nil;
		 }

    func isEmpty() -> Bool {
        return self.root_ == nil;
    }

    func insert(_ key: Double!,_ value: NodeValue!) {
        if (self.isEmpty()) {
            self.root_ = Node(key, value);
			return;
        }
        // Splay on the key to move the last node on the search path for
        // the key to the root of the tree.
        self.splay_(key);
        if (self.root_!.key == key) {
            return;
        }
        let node: Node = Node(key, value);
        if (key > self.root_!.key!) {
            node.left = self.root_;
            node.right = self.root_!.right;
            self.root_!.right = nil;
        } else {
            node.right = self.root_;
            node.left = self.root_!.left;
            self.root_!.left = nil;
        }
        self.root_ = node;
    }

    func remove(_ key: Double) -> Node {
        if (self.isEmpty()) {
            print("Key not found: " + String(key));
			// throws Error;
        }
        self.splay_(key);
        if (self.root_?.key != key) {
            print ("Key not found: " + String(key));
			// throws Error;
        }
        let removed: Node = self.root_!;
        if (self.root_?.left == nil) {
            self.root_ = self.root_!.right;
        } else {
            let right: Node? = self.root_?.right;
            self.root_ = self.root_?.left;
            // Splay to make sure that the new root has an empty right child.
            self.splay_(key);
            // Insert the original right child as the right child of the new
            // root.
            self.root_?.right = right;
        }
        return removed;
    }

    func find(_ key: Double) -> Node? {
        if (self.isEmpty()) {
            return nil;
        }
        self.splay_(key);
        return self.root_!.key == key ? self.root_ : nil;
    }

    func findMax(_ opt_startNode: Node?) -> Node? {
        if (self.isEmpty()) {
            return nil;
        }
        var current: Node? = opt_startNode != nil ? opt_startNode : self.root_;
        while (current != nil && current!.right != nil) {
            current = current!.right!;
        }
        return current;
    }

    func findGreatestLessThan(_ key: Double) -> Node? {
        if (self.isEmpty()) {
            return nil;
        }
        // Splay on the key to move the node with the given key or the last
        // node on the search path to the top of the tree.
        self.splay_(key);
        // Now the result is either the root node or the greatest node in
        // the left subtree.
        if (self.root_ != nil && self.root_!.key! < key) {
            return self.root_!;
        } else if (self.root_ != nil && self.root_!.left != nil) {
            return self.findMax(self.root_!.left);
        } else {
            return nil;
        } }

    func exportKeys() -> [Double] {
        var result = [Double]()
        if !isEmpty() {
            root_!.traverse_ { node in
                result.append(node.key!)
            }
        }
        return result
    }

    func splay_(_ key: Double) {
        if (self.isEmpty()) {
            return;
        }
        // Create a dummy node.  The use of the dummy node is a bit
        // counter-intuitive: The right child of the dummy node will hold
        // the L tree of the algorithm.  The left child of the dummy node
        // will hold the R tree of the algorithm.  Using a dummy node, left
        // and right will always be nodes and we avoid special cases.
        let dummy: Node?;
        var left: Node?;
        var right: Node?;
		dummy = Node(nil, nil);
		left = dummy;
		right = dummy;
        var current: Node? = self.root_;
        while (true) {
            if (current != nil && key < current!.key!) {
                if (current!.left == nil) {
                    break;
                }
                if (key < current!.left!.key!) {
                    // Rotate right.
                    let tmp: Node = current!.left!;
                    current!.left = tmp.right;
                    tmp.right = current;
                    current = tmp;
                    if (current!.left == nil) {
                        break;
                    }
                }
                // Link right.
                right?.left = current;
                right = current!;
                current = current!.left!;
            } else if (current != nil && key > current!.key!) {
                if (current!.right == nil) {
                    break;
                }
                if (key > current!.right!.key!) {
                    // Rotate left.
                    let tmp: Node = current!.right!;
                    current!.right = tmp.left;
                    tmp.left = current;
                    current = tmp;
                    if (current!.right == nil) {
                        break;
                    }
                }
                // Link left.
                left?.right = current;
                left = current!;
                current = current!.right!;
            } else {
                break;
            }
        }
        // Assemble.
        left?.right = current?.left;
        right?.left = current?.right;
        current?.left = dummy?.right;
        current?.right = dummy?.left;
        self.root_ = current;
    }
}

func runBenchmarkSplay()-> Int{
    let benchmark = BenchmarkSplay(name: "Splay", run: runSplay)
    return benchmark.RunSuites(singleItem: "")
}
runBenchmarkSplay()
